Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Remove All Ones With Row and Column Flips II

Problem Statement

Given a 0-indexed m x n binary matrix, return the minimum number of operations needed to remove all 1's from the matrix.

In one operation, you can choose any i and j such that:

  • 0 <= i < m
  • 0 <= j < n
  • grid[i][j] == 1

and change the values of all cells in row i and column j to zero.

Examples

Example 1:

  • Input:
[[1,0,1],
 [1,1,1],
 [0,1,0]]
  • Expected Output: 2
  • Justification: First, choose the cell [0,2], and perform operations. The matrix becomes [[0,0,0],[1,1,0],[0,1,0]]. Then, choose the middle cell [1,1]. The matrix becomes all zeros.

Example 2:

  • Input:
[[0,1,0],
 [1,1,1],
 [0,1,0]]
  • Expected Output: 1
  • Justification: A single operation on the middle cell (cell [1,1]) flips all the 1s to 0s. Thus, only 1 operation is needed.

Example 3:

  • Input:
[[1,1,0,0],
 [1,0,1,0],
 [0,1,1,0],
 [0,0,0,1]]
  • Expected Output: 3
  • Justification: Choose (0, 1), (1, 2), and (3, 3) cells respectively, and convert all values of respected columns and rows to zero.

Solution

To solve this problem, the algorithm employs a recursive depth-first search (DFS) strategy to explore all possible combinations of row and column flips that can lead to a grid with all zeros, starting from any cell containing a '1'. At each step, the algorithm considers a cell with a '1', performs a flip operation (sets all elements in its row and column to '0'), and then recursively checks if the resulting grid can be completely converted to zeros with fewer operations. The key insight here is to explore every possible path of flipping rows and columns from each '1' encountered in the grid, while simultaneously keeping track of the minimum number of flips required. This exhaustive search ensures that all configurations leading to the optimal solution are considered.

The algorithm effectively uses backtracking to undo the flip operations after each recursive call, ensuring that the grid is returned to its previous state before exploring a new path. This approach allows the algorithm to systematically explore all potential combinations of flips, ensuring that no possibility is left unexamined. By comparing the number of flips required for each valid path, the algorithm determines the minimum number of operations needed to convert the entire grid to zeros. This recursive and backtracking method provides a brute-force solution that guarantees finding the minimum number of operations required, albeit with significant computational complexity due to the exploration of all possible flip combinations.

Step-by-Step Algorithm

  1. Initialize Variables: Start with variables to track the minimum number of flips required (minFlips), and arrays to temporarily store the values of a row and a column being flipped (rowValues and colValues).
  2. Iterate Over Grid: Loop through each cell of the grid. For each cell containing a '1', perform the following steps:
    • Preserve Column Values: Save the current values of the column containing the '1' into colValues, and set all its elements to '0'.
    • Preserve Row Values: Similarly, save the current values of the row containing the '1' into rowValues, and set all its elements to '0'.
    • Recursive Call: Recursively call the removeOnes method on the modified grid to find the number of additional flips needed. Add 1 to this number to account for the current flip operation.
    • Track Minimum Flips: Update minFlips with the minimum between its current value and the result of the recursive call.
    • Backtrack: Restore the original values of the row and column from rowValues and colValues to backtrack before moving to the next cell. This step ensures the grid is returned to its state before the flip operation for accurate further exploration.
  3. Base Case and Return: If the function encounters a grid with no '1's (implicitly checked by not finding any '1' during the iteration), it means the grid is already all zeros, and no further operations are needed. In this case, or after exploring all cells, return the minimum number of flips found. If minFlips remains unchanged (i.e., Integer.MAX_VALUE), it indicates that no flips were needed, and the function returns 0.

Algorithm Walkthrough

Given the input grid [[1,0,1], [1,1,1], [0,1,0]], we'll walk through the algorithm step-by-step, including backtracking steps. The goal is to find the minimum number of operations needed to convert all '1's to '0's by flipping all elements in any row or column containing a '1'.

Initial Setup

Input grid:

[[1,0,1], 
 [1,1,1], 
 [0,1,0]]

Step-by-Step Walkthrough

  1. Start with the first cell (0,0) containing '1':

    • Preserve column and row before flipping:
      • Column before flip: 1,1,0 (Column 0)
      • Row before flip: 1,0,1 (Row 0)
    • Perform flip operation:
      • New grid after flip: [[0,0,0], [0,1,1], [0,1,0]]
    • Recursive call with the new grid.
  2. Recursive call depth 1:

    • The grid now looks like: [[0,0,0], [0,1,1], [0,1,0]]
    • Move to the next cell with '1', which is (1,1):
      • Preserve column and row before flipping:
        • Column before flip: 0,1,1 (Column 1)
        • Row before flip: 0,1,1 (Row 1)
      • Perform flip operation:
        • New grid after flip: [[0,0,0], [0,0,0], [0,0,0]]
      • Recursive call with the new grid.
  3. Recursive call depth 2 (Base Case Reached):

    • The grid is now all zeros: [[0,0,0], [0,0,0], [0,0,0]]
    • Since the grid is all zeros, no further operations are needed. Return 0 + current operation count (2).
    • minFlips = 1 + min(INT_MAX, 1) = 2.
  4. Backtrack from depth 2 to depth 1:

    • Restore the grid to the state before the last flip operation:
      • Grid before backtrack: [[0,0,0], [0,0,0], [0,0,0]]
      • Grid after backtrack: [[0,0,0], [0,1,1], [0,1,0]]
    • Continue exploring other possibilities, although, in this case, all '1's have been flipped already.
  5. Move to the next cell with '1', which is at (1,2):

    • Preserve column and row before flipping:
      • Column before flip: 0,1,0 (Column 2)
      • Row before flip: 0,1,1 (Row 1)
    • Perform flip operation:
      • New grid after flip: [[0,0,0], [0,0,0], [0,1,0]]
    • Recursive call with the new grid.
  6. Recursive call depth 1 for cell (1,2):

    • The grid now looks like: [[0,0,0], [0,0,0], [0,1,0]]
    • Move to the next '1', which is at (2,1). It returns 1 operation.
  7. Backtrack from depth 3 to depth 1:

    • Restore the grid to the state before the last flip operation:
      • Grid before backtrack: [[0,0,0], [0,0,0], [0,0,0]]
      • Grid after backtrack: [[0,0,0], [0,1,1], [0,1,0]]
    • minFlips = 1 + min(1, 2) = 2.
  8. Explore (2, 1) at depth 1:

  • minFlips = 1 + min(1, 2) = 2.
  1. Keep exploring other points at depth 1.

  2. Final result We need to perform minimum 2 operations to flip al 1's to 0 according to the given rules.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • Worst-case scenario: The algorithm iterates through every cell of the grid, attempting to flip each '1' it encounters and recursively solving the modified grid. In the worst case, this approach could explore nearly every combination of flips for a grid filled with '1's.
  • Given a grid of size (m * n), the worst-case time complexity can approach , considering each cell flip could lead to a recursive call (although not all flips will result in a recursive call due to the base case check).

Space Complexity:

  • Worst-case scenario: The recursion depth can go up to (mn) in theory, if each cell's flip leads to a unique recursive call. However, practical limits on recursion depth and the fact that many paths will be pruned early mean actual usage may be less.
  • Auxiliary space: It is used for storing the row and column values for backtracking, leading to .
  • Total Space Complexity: due to the grid copy (implicit in recursion stack) and the auxiliary space for row and column preservation during backtracking.
Remove All Ones With Row and Column Flips II (medium)
Reverse Integer (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Initial Setup

Step-by-Step Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: